package com.blankj.easy._0001;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 五分钟思考法：如果一道题如果 5 分钟之内有思路，就立即动手写代码解题。
 * 如果 5 分钟之后还没有思路，就直接去看题解。然后根据题解的思路，自己去实现代码。
 * 如果发现自己看了题解也无法实现代码，就认真阅读题解的代码，并理解代码的逻辑。
 *
 * <pre>
 *     author: Blankj
 *     blog  : http://blankj.com
 *     time  : 2017/04/21
 *     desc  :Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 * You may assume that each input would have exactly one solution, and you may not use the same element twice.
 * 描述：给定一个整数数组numsnums 和一个整数目标值targettarget。
 * 要求：在该数组中找出和为targettarget 的两个整数，并输出这两个整数的下标。可以按任意顺序返回答案。
 * </pre>
 */
public class Solution {

//    思路：查找时，建立索引（Hash查找）或进行排序（二分查找）。本题缓存可在找的过程中建立索引，故一个循环可以求出解（总是使用未
//    使用元素查找使用元素，可以保证每一对都被检索到）
//    思路 2：哈希表
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; ++i) {
            final Integer value = map.get(nums[i]);
            if (value != null) {
                return new int[] { value, i };
            }
            map.put(target - nums[i], i);
            System.out.println(map);
        }
        return null;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{11, 7, 11, 2};
        int target = 9;
        System.out.println(Arrays.toString(solution.twoSum(nums, target)));
    }
}
